import java.util.ArrayList;

/**
 * 使用插入排序的桶排序
 */
public class InsertToBucketingSort {

    public void sort(int[] nums, int bucketCount) {
        // 找到最大和最小值
        // 用来计算索引偏移量和除数
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(num, min);
            max = Math.max(num, max);
        }
        int offset = -min;
        // 计算理论上每个桶需要装的元素的个数
        int bucketSize = (max - min) / bucketCount + 1;
        // 初始化桶
        ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素分配到桶中
        for (int num : nums) {
            // 用除法向下取整的方法计算桶的索引
            int index = (num + offset) / bucketSize;
            buckets[index].add(num);
        }

        // 对每个桶中的元素进行排序
        for (int i = 0; i < bucketCount; i++) {
            insertSort(buckets[i]);
        }

        // 合并有序桶
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            for (Integer num : buckets[i]) {
                nums[index++] = num;
            }
        }
    }

    // 插入排序算法
    private void insertSort(ArrayList<Integer> nums) {
        int sortedIndex = 0;
        while (sortedIndex < nums.size()) {
            for (int i = sortedIndex; i > 0; i--) {
                if (nums.get(i) < nums.get(i - 1)) {
                    int temp = nums.get(i);
                    nums.set(i, nums.get(i - 1));
                    nums.set(i - 1, temp);
                } else {
                    break;
                }
            }

            sortedIndex++;
        }
    }
}
